//汉诺塔
//经过测试得出，n个盘子，至少需要移动2^n-1次
public class Test {
    public static void main(String[] args) {
        hanoi(1,'A','B','C');
        System.out.println();
        hanoi(2,'A','B','C');
        System.out.println();
        hanoi(3,'A','B','C');
    }

    /**
     *
     * @param n n个盘子
     * @param pos1 起始位置
     * @param pos2 中转位置
     * @param pos3 目标位置
     */
    public static void hanoi(int n,char pos1,char pos2,char pos3){
        if(n==1){
            move(pos1,pos3);
            return ;   //不能省略，否则会死循环
        }
        hanoi(n-1,pos1,pos3,pos2);
        move(pos1,pos3);
        hanoi(n-1,pos2,pos1,pos3);
    }

    /**
     *
     * @param start 起始位置
     * @param end   目标位置
     */
    public static void move(char start,char end){
        System.out.print(start+"->"+end+"  ");
    }
}

//青蛙跳台阶
//1、一次可以跳1或2级台阶
class Test2 {
    public static void main(String[] args) {
        System.out.println(steps(5));
    }
    public static int steps(int n){
        if (n == 1) {
            return 1;
        } else if (n==2) {
            return 2;
        } else if (n>2) {
            return steps(n-1)+steps(n-2);
        }else{   //n<=0
            return 0;
        }
    }
}

//1、一次可以跳n级台阶
class Test3 {
    public static void main(String[] args) {
        System.out.println(steps(4));
    }
    public static int steps(int n){
        if (n == 1) {
            return 1;
        } else if (n>1) {
            return 2*steps(n-1);
        }else{   //n<=0
            return 0;
        }
    }
}